package com.aaron.leetcode.lc05;

/**
 * @author liurong
 * @date 2022/1/21 18:43
 * @version:
 */
/*
    状态转移方程，递归|迭代
    重叠子问题，备忘录

    自顶向下动态规划解法（递归）

    自底向上的迭代解法
 */
import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution05_1 {

    //状态转移方程
    //s = "babad"

    /*
        m:左指针，n右指针
        递归：自顶向下
        memo[m][n] = 1/0 是否是回文串 -1为初始化值
        long(s) = long(sub(m,n))
     */

    //重叠子问题

    int[][] memo;

    //左右指针初始化为0,0
    int left = 0;

    int right = 0;


    public String longestPalindrome(String s) {

        int length = s.length();
        memo = new int[length][length];
        for (int i = 0; i < length; i++) {
            //0代表false，不是回文子串
            Arrays.fill(memo[i], -1);
        }
        dp(s, 0, length - 1);
        return s.substring(left, right + 1);

    }


    boolean dp(String s, int m, int n) {
        if (m > n) {
            return false;
        }
        if (m == n) {
            memo[m][n] = 1;
            return true;
        }
        if (memo[m][n] == 1) {
            return true;
        }
        if (memo[m][n] == 0) {
            return false;
        }
        dp(s, m + 1, n);

        dp(s, m, n - 1);
        boolean isPalindrome;
        //cbba这种情况，如果bb相等，内部没有其他字符串则直接返回true
        if (s.charAt(m) == s.charAt(n) && m + 1 == n) {
            isPalindrome = true;
        } else {
            isPalindrome = s.charAt(m) == s.charAt(n) && dp(s, m + 1, n - 1);
        }

        if (isPalindrome) {
            memo[m][n] = 1;
            if (right - left < n-m) {
                left = m;
                right = n;
            }
        } else {
            memo[m][n] = 0;
        }
        return isPalindrome;
    }
    //cbbd

    public static void main(String[] args) {
        Solution05_1 solution05_1 = new Solution05_1();
        String s = "cbbd";
        System.out.println(solution05_1.longestPalindrome(s));
    }


}

